package everydayGrade.t1;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @Author: Siantar
 * @Date: 2023-11-27-22:35
 * @Description: 1.0
 */
public class T0907 {
    public int sumSubarrayMins(int[] arr) {
        int n = arr.length, res = 0, MOD = 1_000_000_007;
        int[] dp = new int[n];
        Deque<Integer> deque = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            while (!deque.isEmpty() && arr[deque.peek()] > arr[i]) {
                deque.pop();
            }
            int k = i - (deque.isEmpty() ? -1 : deque.peek());
            dp[i] = k * arr[i] + (deque.isEmpty() ? 0 : dp[i - k]);
            res = (res + dp[i]) % MOD;
            deque.push(i);
        }
        return res;
    }
}
